package oct2013.linkednode;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author Yinzi Chen
 * @date Nov 7, 2013
 */
public class BinaryTreePostorderTraversal {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.peek();
                if (cur.right == null) {
                    cur = stack.pop();
                    res.add(cur.val);
                    while (!stack.isEmpty() && stack.peek().right == cur) {
                        cur = stack.pop();
                        res.add(cur.val);
                    }
                    cur = null;
                } else {
                    cur = cur.right;
                }
            }
        }
        return res;
    }
}
